﻿public class TreeNode {     
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
}

public class Solution
{

    private int result;
    public int MinCameraCover(TreeNode root) 
    {
        // 1未覆盖，2相机位置，3覆盖

        if (traversal(root) == 1)
        {
            result++;
        }

        return result;
    }

    private int traversal(TreeNode node)
    {
        if (node is null) return 3;
        
        int left = traversal(node.left);
        int right = traversal(node.right);
        if (left == 3 && right == 3)
        {
            return 1;
        }
        
        if (left == 1 || right == 1)
        {
            result++;
            return 2;
        }
        if (left == 2 || right == 2)
        {
            return 3;
        }
        return -1;
    }

    public static void Main(string[] args)
    {
        int?[] numRoot = [0, 0, null, 0, null, 0, null, null, 0];
        TreeNode root = CreateBinaryTree(numRoot);

        Solution solution = new Solution();
        int res = solution.MinCameraCover(root);
        Console.WriteLine(res);
    }

    private static TreeNode CreateBinaryTree(int?[] numRoot)
    {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        TreeNode root = new TreeNode(numRoot[0].Value);
        queue.Enqueue(root);

        TreeNode node;
        int i = 1;
        while (i < numRoot.Length)
        {
            bool flag = true;
            node = queue.Dequeue();
            if (numRoot[i] is not null)
            {
                flag = false;
                node.left = new TreeNode(numRoot[i].Value);
                queue.Enqueue(node.left);
            }
            i++;

            if (i >= numRoot.Length) break;
            if (numRoot[i] is not null)
            {
                flag = false;
                node.right = new TreeNode(numRoot[i].Value);
                queue.Enqueue(node.right);
            }
            i++;

            if (flag) queue.Enqueue(node);
        }

        return root;
    }
    
}